package answer_1_10

import (
	"fmt"
	"math"
	"sort"
)

//给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
//算法的时间复杂度应该为 O(log (m+n)) 。

//示例 1：
//输入：nums1 = [1,3], nums2 = [2]
//输出：2.00000
//解释：合并数组 = [1,2,3] ，中位数 2

//示例 2：
//输入：nums1 = [1,2], nums2 = [3,4]
//输出：2.50000
//解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

//提示：
//nums1.length == m
//nums2.length == n
//0 <= m <= 1000
//0 <= n <= 1000
//1 <= m + n <= 2000
//-106 <= nums1[i], nums2[i] <= 106

func Answer_4() {
	fmt.Println(findMedianSortedArrays_1([]int{1, 2}, []int{3, 4}))
}

func findMedianSortedArrays_1(nums1 []int, nums2 []int) float64 {
	nums := append(nums1, nums2...)
	sort.Ints(nums)
	num := len(nums)
	left := num / 2
	right := 0
	if num%2 > 0 {
		return float64(nums[left])
	} else {
		left = left - 1
	}
	right = left + 2
	ints := nums[left:right]
	s := float64(ints[0]+ints[1]) / float64(2)
	return s
}

func findMedianSortedArrays_2(a, b []int) float64 {
	if len(a) > len(b) {
		a, b = b, a // 保证下面的 i 可以从 0 开始枚举
	}

	m, n := len(a), len(b)
	a = append([]int{math.MinInt}, append(a, math.MaxInt)...)
	b = append([]int{math.MinInt}, append(b, math.MaxInt)...)

	// 枚举 nums1 有 i 个数在第一组
	// 那么 nums2 有 (m + n + 1) / 2 - i 个数在第一组
	i, j := 0, (m+n+1)/2
	for {
		if a[i] <= b[j+1] && a[i+1] > b[j] { // 写 >= 也可以
			max1 := max(a[i], b[j])     // 第一组的最大值
			min2 := min(a[i+1], b[j+1]) // 第二组的最小值
			if (m+n)%2 > 0 {
				return float64(max1)
			}
			return float64(max1+min2) / 2
		}
		i++ // 继续枚举
		j--
	}
}
